class Solution {
    // //该时间复杂度O(n^2)
    // public int Hight(TreeNode root){
    //     if(root == null){
    //         return 0;
    //     }
    //     int leftHight = Hight(root.left);
    //     int rightHight = Hight(root.right);
    //     return (leftHight>rightHight ? leftHight : rightHight) +1;
    // }
    // public boolean isBalanced(TreeNode root) {
    //     if(root == null){
    //         return true;
    //     }
    //     return Math.abs(Hight(root.left)-Hight(root.right))<2 &&isBalanced(root.left)&&isBalanced(root.right);
    // }

    //要求时间复杂度O(n);
    public int Hight(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHight = Hight(root.left);
        int rightHight = Hight(root.right);
        if(leftHight>=0&&rightHight>=0&&Math.abs(leftHight-rightHight)<2){
            return (leftHight>rightHight ? leftHight : rightHight) +1;
        }else{
            return -1;
        }
    }
    public boolean isBalanced(TreeNode root){
        return Hight(root)!= -1;
    }
}